/**
 * @author 徐楠
 * @date 2022/4/10 13:22
 * @version 1.0
 */

package com.xunan.likou;

import java.util.*;

public class MatrixZeroing {
    public static void main(String[] args) {
        //int[][] matrix = {{1,1,1},{1,0,1},{1,1,1}};
        //int[][] matrix = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        int[][] matrix = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        setZeroes(matrix);
        for (int[] ints : matrix) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }

    public static void setZeroes(int[][] matrix) {
        int x = matrix.length;
        int y = matrix[0].length;
        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (matrix[i][j] == 0) {
                    //上
                    int top = i - 1;
                    //下
                    int bottom = i + 1;
                    //左
                    int left = j - 1;
                    //右
                    int right = j + 1;

                    int count = 0;
                    while (count < x + y - 1) {
                        if (top >= 0 && matrix[top][j] != 0) {
                            List<Integer> orDefault = map.getOrDefault(top, new ArrayList<>());
                            orDefault.add(j);
                            map.put(top, map.getOrDefault(top, orDefault));
                            top--;
                        }
                        if (bottom <= x - 1 && matrix[bottom][j] != 0) {
                            List<Integer> orDefault = map.getOrDefault(bottom, new ArrayList<>());
                            orDefault.add(j);
                            map.put(bottom, map.getOrDefault(bottom, orDefault));
                            bottom++;
                        }
                        if (left >= 0 && matrix[i][left] != 0) {
                            List<Integer> orDefault = map.getOrDefault(i, new ArrayList<>());
                            orDefault.add(left);
                            map.put(i, map.getOrDefault(i, orDefault));
                            left--;
                        }
                        if (right <= y - 1 && matrix[i][right] != 0) {
                            List<Integer> orDefault = map.getOrDefault(i, new ArrayList<>());
                            orDefault.add(right);
                            map.put(i, map.getOrDefault(i, orDefault));
                            right++;
                        }

                        count++;
                    }
                }

            }
        }

        Set<Map.Entry<Integer, List<Integer>>> entries = map.entrySet();
        for (Map.Entry<Integer, List<Integer>> entry : entries) {
            Integer key = entry.getKey();
            List<Integer> value = entry.getValue();
            for (Integer integer : value) {
                matrix[key][integer] = 0;
            }
        }

    }
}
